Batch 3 - Class 260 - Game Theory

• Think about one more game that you like, which can be modeled as Markov Chain. Think about what "states" represent, and how you would create a transition diagram. Think about the elements you would take into account to assign probabilities to transition. Finally, on a simplistic version, try to find probabilities of outcomes. What outcomes are important in your game?

• You have three players, A, B and C with one bullet each, and chances of successfully shooting a target 10%, 90% and 60% of the time. They will take turns at trying to shoot each other. What should A do?
• Answer: A should purposefully miss the shot (Get the intuition right first, then get the math)
• Game of sharing rewards - There are two finalists tied in a game. Total reward of $50000. Are are asked separately if they would share the reward. If both say they would share, the reward would be shared. If one said share, and the other said he won't, the latter gets the whole $50000. If both said they won't share, no one gets anything.
• Let kids play and try to figure out what kids do.
• What is the best strategy?
• Does it help if people are allowed to talk to each other before making a decision?
• One possible strategy - tell the other guy you are not going to share here, but give him money later?
• What if in case of share/won't share, the winner gets $60000?
• Practical application - Advertising spends. Competitive advertising spends are not believed to yield results, they cancel out. If both advertise or none advertise, no gain. If one advertises, the gains are huge. How do you plan your advertising?
• Practical application, overtaking from the wrong lane... Let kids think about it.
• Prisoners' Dilemma - Two prisoners, both being asked to tell who did the crime. If both don't confess, they just stay in jail for 5 years. If one rats out, he is set free and the other person is hanged. If both confess, both of them are given a 10 year jail. What should they do?
• Draw the choice matrix and rewards for each. 
• What should prisoner 1 do if he believes that prisoner 2 will confess? What should he do if he believes that prisoner 2 will not confess? Similarly, what should prisoner 2 reason? What will be the outcome of this game?
• The dominant strategy here is for both players to confess. This is called Nash equilibrium. Each player is playing the best response to the other person's chosen strategy. Each player is reacting best to what they think the other person will do.
• Equilibrium outcomes are not necessarily the best! There is a better outcome for both if they cooperate.
• How can cooperation be sustained in real world?
• In repeated games, people have chance of testing waters.
• Go back to advertising choices - if over time no one deviates from normal ad spend, cooperation sets in
• Possible Strategy? Tit for tat!
• The Meeting Game: Husband and wife have left their cellphone at home, and need to figure out where to meet in the evening - either dinner or movie. If both go to dinner, they are both very happy. If they both go to movie, both are ok. If they miss each other, they are sad. (20,20   0,0    0,0     10,10 matrix)
• Evaluate this using each person's decision tree - No dominant strategy!
• What is the equilibrium? There are two equilibriums... We don't know which one is going to happen.
• Both could choose 20,20. If both were 10,10 then no way to guess
• Rock, Paper, Scissor: Tie gives 0 to each; If unequal, then +2 and -1. Let kids analyze the game and find out the best strategy.
• All mixed strategy
• But unlike previous game, no incentive to cooperate
• Zero sum Games
• The best strategy is to keep the other person guessing!

• (Answer) Let the Admiral leave with 2 assistants. Once they have walked for 1 day, one assistant may return with 1 day's worth of food and leave the Admiral and his other assistant with enough for 4 days each. The next day, the second assistant may return safely with 2 day's worth of supplies leaving one day's worth to Perry who now has enough for the 4 remaining days.

• How many days would it take him if he was all by himself?
• Answer: 12 days instead of 6, if we assume that food can be dropped along the way, hidden from wild beasts. Perry starts carrying 4 units (4u=4 days' worth of supplies) walks 1d, leaves 2u in a stash and returns to Shungnak. He does the same thing again so there are now 4u in the stash. He may now start his final journey with 4u: he walks 1d (using 1u) and picks up 1u at the stash (3u remain), sopoo he may carry 4u, walk another day and leave 2u in a second stash, before returning to the first stash where he picks up the remaining 3u. He walks one day to arrive with 2u to the second stash. He picks up the 2u that were stored there to walk away with 4u, which is enough to complete the trip (since the second stash is 4d away from the goal).